package com.ly.algorithm.DataStructures.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @Classname Graph
 * @Description TODO
 * @Date 2020/5/3 18:32
 * @Author 冷心影翼
 */
public class Graph {

    private ArrayList<String> vertexList;  //顶点集合

    private int[][] edges;  //临接矩阵

    private int numOfEdges;

    private boolean[] isVisited ;

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.insertVertex("A");
        graph.insertVertex("B");
        graph.insertVertex("C");
        graph.insertVertex("D");
        graph.insertVertex("E");
        graph.insertEdge(0,2,1);
        graph.insertEdge(0,3,1);
        graph.insertEdge(0,4,1);
        graph.insertEdge(1,2,1);
        graph.insertEdge(1,3,1);
        graph.insertEdge(1,4,1);
        graph.showGraph();
        graph.dfs();
        graph.bfs();
    }

    public Graph(int n) {
        edges = new int[n][n];
        numOfEdges = 0;
        vertexList = new ArrayList<>(n);
    }

    public void showGraph() {
        for(int[] c: edges) {
            System.out.println(Arrays.toString(c));
        }
    }

    public int getNumOfVertex() {
        return vertexList.size();
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    public int getWeight(int v1,int v2) {
        return edges[v1][v2];
    }

    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    public void insertEdge(int v1,int v2,int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    public int getFirstNeighbor(int v1) {
        for (int v2 = 0; v2< vertexList.size();v2++) {
            if(edges[v1][v2] == 1) {
                return v2;
            }
        }
        return -1;
    }

    public int getNextNeighbor(int v1,int v2)  {
        for (int i = v2+1; i < vertexList.size();i++) {
            if(edges[v1][i] == 1) {
                return i;
            }
        }
        return -1;
    }


    public void dfs() {
        isVisited = new boolean[vertexList.size()];
        for(int i=0;i<vertexList.size();i++) {
            if(!isVisited[i]){
                dfs(i);
            }
        }
        System.out.println();
    }
    public void dfs(int v1) {
        System.out.print(vertexList.get(v1)+" ");
        int v2 = getFirstNeighbor(v1);
        isVisited[v1] = true;
        while(v2!=-1) {
            if(!isVisited[v2]) {
                dfs(v2);
            }
            v2 = getNextNeighbor(v1,v2);
        }
    }

    public void bfs() {
        isVisited = new boolean[vertexList.size()];
        for(int i=0;i<vertexList.size();i++) {
            if(!isVisited[i]){
                bfs(i);
            }
        }
        System.out.println();
    }
    public void bfs(int v1) {
        int u;
        int v2;
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.print(vertexList.get(v1)+" ");
        queue.add(v1);
        isVisited[v1] = true;
        while (!queue.isEmpty()) {
            u = queue.removeFirst();
            v2 = getFirstNeighbor(u);
            while (v2!=-1) {
                if(!isVisited [v2]) {
                    System.out.print(vertexList.get(v2)+" ");
                    isVisited[v2] = true;
                    queue.addLast(v2);
                }
                v2 = getNextNeighbor(u,v2);
            }
        }
    }
}
